//== SAGITTARIUS ============================================================================

//== FILEDOC =========================================================================

/** @file sm.h
  * @brief Contains target-independent backend for the DFA generator
  */

//== BEGINNING OF CODE ===============================================================

#ifndef __SAGUTTARUIS__SM__H_
#define __SAGUTTARUIS__SM__H_

//== INCLUDES ========================================================================

#include "sagittarius/core/SagittariusCore.h"
#include "sagittarius/lexer/dfa.h"
#include "sagittarius/unicode/CUnicode.h"

#ifdef __cplusplus
extern "C" {
#endif

/// @brief The size of the physical single-tier tables
#define SM_ITABLE_SIZE 256

/// @brief Does the table actually exist?
#define SM_ITABLE_EXISTS_FLAG 0x10000000

/// @brief Match exists in current tier - advance to lower level
#define SM_ITABLE_CONTINUE_FLAG 0x10000000

/// @brief Word size for tier
typedef uint32 sm_tier_type;

/** @brief Mask for the actual state/table number from lookups
 * @details As opposed to flags like @ref SM_ITABLE_EXISTS_FLAG,
 * which are embedded in the word
 */
#define SM_LOOKUP_MASK 0x0FFFFFFF

/** @brief The type used in indirection tables
 * @details The word type used for this typedef determines
 * an upper bound on the possible number of states. Furthermore,
 * we can't use all the bits in this word, since some are reserved
 * to indicate continuation, existence of a leaf node, etc. 
 * See @ref SM_ITABLE_EXISTS_FLAG & others.
 */
typedef uint32 sm_itype;

/** 
 * @brief Single branch for the indirection table
 */
typedef struct __sm_itable_single{
    /// @brief Actual indirection table
    sm_itype itbl[SM_ITABLE_SIZE];
    
} sm_itable_single;

/** 
 * @brief Single branch for the indirection table
 */
typedef struct {
    /// @brief Number of tables
    sm_tier_type n;
    
    /// @brief Array of single tables
    sm_itable_single* leafs;
} sm_itable_branch;

/** 
 * @brief State transition table top level
 * @details Multi-tier indirection table for DFA state transitions.
 * Contains one branch (@ref sm_itable_branch) per tier, with each 
 * branch containing possibly many individual lookup tables 
 * (implemented by @ref sm_itable_single).
 * See See @ref TransitionTableTiers "Transition Table Tiers" for more information
 * about tiers
 */
typedef struct {
    /// @brief Number of tiers
    sm_tier_type n;
    
    /// @brief Array of branches
    sm_itable_branch* b;
    
    uint32 offset;
    //sm_tier_type shift_level;
} sm_itable;

/**
 * @page TransitionTableTiers Transition Table Tiers
 * The transition table is based on the concept of tiers, with the
 * topmost tier representing the most significant byte in the set of
 * transitions for state @a n. For example, if a state had transitions
 * on "a" (0x0061) and "事" (0x4e8b), then there would be two tiers (
 * since the characters use at most two bytes) with tier 2 (the top
 * tier) containing entries for 0x00 and 0x4e. These would point to
 * two different tier 1 tables, one having an entry for 0x61 "a" and
 * one having an entry of 0x8b (the second byte of "事").
 */

/*typedef struct {
    sm_tier_type shift_level;
} sm_stateformat;*/

/** @brief Target-independent state machine holding transition tables etc.
 */
typedef struct {
    ///Transition table for states
    sm_itable** stbl;
    //sm_stateformat* sf;
    
    ///DFA copy: does not get deallocated by SM destructor
    const dfarep* dfa;
} smrep;

/**
 * @{
 */

/**
 * @brief Fetches or creates the entry in the transition table for a symbol
 * @param[in] a The symbol that forms the base of the transition
 * @param[in] tostate The state to transition to when symbol @a a is encountered on the input
 * @param[in] tier The tier to search. Clients should always pass tier=1.
 * The function will call itself recursively with higher tier values where
 * applicable.
 * @param[in,out] tbl The transition table. May be modified to include a new
 * table and/or entry for @a a.
 * @returns Lookup info for @a a in @a tbl. Can contain either a state number
 * or a table number, along with flags. Use @ref SM_LOOKUP_MASK to get just
 * the number.
 */
sm_itype sm_ttable_fetch(LXAlphaType a, sm_itype tostate, sm_tier_type tier, sm_itable* tbl);

/// @}

/**
 * @brief State machine target-independent backend
 * @param[in]  dfa State machine representation
 * @returns State machine representation. Use for specific backends
 * like @ref dfa2sm_c
 */
smrep* dfa2sm(const dfarep* dfa);

/**
 * @brief State machine destructor
 * @param[in,out] sm SM to be destroyed
 */
void destroy_sm(smrep* sm);

#ifdef __cplusplus
}//extern "C"
#endif

#endif
